In [1]:
import numpy as np
from sklearn.datasets import load_digits
from sklearn.ensemble import RandomForestClassifier
from sklearn.metrics import accuracy_score
В этом задании будет использоваться датасет digits из sklearn.datasets. Оставьте последние 25% объектов для контроля качества, разделив X и y на X_train, y_train и X_test, y_test.
In [2]:
#Loading digits dataset
digits = load_digits()
X = digits.data
y = digits.target
In [3]:
print(digits.DESCR)
In [4]:
#Splitting on train and test datasets
p = 0.75
idx = int(p * X.shape[0]) + 1
X_train, X_test = np.split(X, [idx])
y_train, y_test = np.split(y, [idx])
Целью задания будет реализовать самый простой метрический классификатор — метод ближайшего соседа, а также сравнить качество работы реализованного вами 1NN с RandomForestClassifier из sklearn на 1000 деревьях.
Реализуйте самостоятельно метод одного ближайшего соседа с евклидовой метрикой для задачи классификации. Можно не извлекать корень из суммы квадратов отклонений, т.к. корень — монотонное преобразование и не влияет на результат работы алгоритма.
Никакой дополнительной работы с признаками в этом задании делать не нужно — мы еще успеем этим заняться в других курсах. Ваша реализация может быть устроена следующим образом: можно для каждого классифицируемого объекта составлять список пар (расстояние до точки из обучающей выборки, метка класса в этой точке), затем сортировать этот список (по умолчанию сортировка будет сначала по первому элементу пары, затем по второму), а затем брать первый элемент (с наименьшим расстоянием).
Сортировка массива длиной N требует порядка N log N сравнений (строже говоря, она работает за O(N log N)). Подумайте, как можно легко улучшить получившееся время работы. Кроме простого способа найти ближайший объект всего за N сравнений, можно попробовать придумать, как разбить пространство признаков на части и сделать структуру данных, которая позволит быстро искать соседей каждой точки. За выбор метода поиска ближайших соседей в KNeighborsClassifier из sklearn отвечает параметр algorithm — если у вас уже есть некоторый бэкграунд в алгоритмах и структурах данных, вам может быть интересно познакомиться со структурами данных ball tree и kd tree.
Доля ошибок, допускаемых 1NN на тестовой выборке, — ответ в задании 1.
In [5]:
def euclidian_metric(x, y):
return np.sqrt( np.sum((x - y)**2) )
In [6]:
y_pred_knn = []
for test_value in X_test:
ind_min_metric = 0
min_metric = euclidian_metric(test_value, X_train[0])
for index, train_value in enumerate(X_train):
metric = euclidian_metric(test_value, train_value)
if metric < min_metric:
min_metric = metric
ind_min_metric = index
y_pred_knn.append(y_train[ind_min_metric])
In [7]:
#Accuracy
knn_err_rate = 1 - accuracy_score(y_test, y_pred_knn)
print('1nn classifier error: ' + str(knn_err_rate))
In [8]:
with open('answer1.txt', 'w') as fout:
fout.write(str(knn_err_rate))
Теперь обучите на обучающей выборке RandomForestClassifier(n_estimators=1000) из sklearn. Сделайте прогнозы на тестовой выборке и оцените долю ошибок классификации на ней. Эта доля — ответ в задании 2. Обратите внимание на то, как соотносится качество работы случайного леса с качеством работы, пожалуй, одного из самых простых методов — 1NN. Такое различие — особенность данного датасета, но нужно всегда помнить, что такая ситуация тоже может иметь место, и не забывать про простые методы.
In [9]:
#Random forest classifier
rf_clf = RandomForestClassifier(n_estimators=1000)
rf_clf.fit(X_train, y_train)
Out[9]:
In [10]:
#Random forest prediction
y_pred_rf = rf_clf.predict(X_test)
#Accuracy
rf_err_rate = 1 - accuracy_score(y_test, y_pred_rf)
print('Random forest classifier error: ' + str(rf_err_rate))
In [11]:
with open('answer2.txt', 'w') as fout:
fout.write(str(rf_err_rate))